package com.ztom.v2;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangTao
 */
public class Code53CourseSchedule {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 入度表
        int[] in = new int[numCourses];
        // 构建邻接表
        List<Integer>[] next = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            next[i] = new ArrayList<>();
        }

        // 0 依赖 1, 0 入度+1, 0 挂在 1 的邻接表下
        for (int[] prerequisite : prerequisites) {
            in[prerequisite[0]]++;
            next[prerequisite[1]].add(prerequisite[0]);
        }

        // BFS 先找到入度为 0 的点 入队列
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.addLast(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer cur = queue.pollFirst();
            // 删除当前点: 修完当前课程
            numCourses--;
            // 邻接表的点入度减 1
            for (Integer c : next[cur]) {
                if (--in[c] == 0) {
                    queue.addLast(c);
                }
            }
        }
        return numCourses == 0;
    }
}
